package 力扣面试经典150;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-04-17
 * Time:15:13
 */

/**
 * 力扣面试经典150:52. N 皇后 II
 * 困难
 * 相关标签
 * 相关企业
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * 给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
 * 示例 1：
 * 输入：n = 4
 * 输出：2
 * 解释：如上图所示，4 皇后问题存在两个不同的解法。
 */
public class totalNQueens {
    int count = 0;
    boolean[] colhasused,dig1,dig2;
    public int totalNQueens(int n) {
        //都不能在同一列，且相邻两行的不能为相邻两列
        colhasused = new boolean[n];
        //主对角线，这里的主对角线是运用了坐标轴来表示的，主对角线在坐标轴上表示在 y = x + b上的，对应row，col就是row = col - b
        //但是针对主对角线这里会变成 y - x = b 会出现负值的情况，我们需要加上一个 n就不会出现了
        dig1 = new boolean[2 * n];
        dig2 = new boolean[2 * n];//副对角线同上
        dfs(0,n);
        return count;
    }
    public void dfs(int row,int n){
        if(row >= n){
            count++;
            return;
        }
        for(int col = 0;col < n;col++){
            if(!colhasused[col] && !dig1[row - col + n] && !dig2[row + col]){
                colhasused[col] = dig1[row - col + n] = dig2[row + col] = true;
                dfs(row + 1,n);
                colhasused[col] = dig1[row - col + n] = dig2[row + col] = false;
            }
        }
    }
}
